﻿#region Using directives

using System;
using System.Collections.Generic;
using System.Text;

#endregion

namespace Hoshimi._TSP_
{
    public interface IGNode<T> where T:IGNode<T>
    {
        
        /*
        parent
         ^
         |
         |
         |
         |
        thisNode   ------> nextSibling()
         |
         |
         |
         | 
         V
        firstChild()

        */

        T firstChild();
        T nextSibling();
        T parent
        {
            get;
            set;
        }
    }

    public class GraphException: ApplicationException
    {
        public GraphException(string msg):base (msg)
        {
        }
    }

    public class Graph<T>: IComparer<T> where T: class, IGNode<T>  
        //it is intended that T not be a value type
    {
        
        public T root			= default(T);   //which is to say, NULL if a ref object 0's/null if a struct

        T lastNode				= default(T);      //lastNode returned in search

        bool endOfGraph			= false;
        List<T> theOpenNodes;   //used in breathFirst()
        List<T> nextGeneration	= null; //these nodes were delivered: get children
        Comparison<T> sorter	= null;
        bool isAstar			= false;
        bool rmvParents			= false;

        int maxNodes = -1;

        public Graph(T rootNode)
        {
                //this constructor used for DFS
            root = rootNode;
        }

        public Graph(T rootNode, Comparison<T> sortr): this(rootNode)
        {
                //this constructor used for A* search, greedy search
                //and bestFirst search
            sorter = sortr;
        }

        public Graph(T rootNode, Comparison<T> sortr, int cutOff):
            this(rootNode, sortr)
        {
                //this constructor used for beam search
                //for a beam search with infinite cutoff: use bestFirst
            if (cutOff <= 0)
                throw new GraphException("cutOff not > 0");
            maxNodes = cutOff;
        }

        public int cutOff
        {
            get { return maxNodes; }
            set { maxNodes = value; }
        }

        public bool removeParents   //when graph no longer needs them
        {
            get { return rmvParents; }
            set { rmvParents = value; }
        }

        public IEnumerable<T> Astar()
        {
            reset();
            if (sorter == null)
                throw new GraphException("comparator not supplied for Astar");
            isAstar = true;

            placeRoot(theOpenNodes);
            yield return root;

            while (true)
            {
                T aNode = nextNode(ref theOpenNodes, ref theOpenNodes);
                if (aNode == null)
                    break;
                yield return aNode;
                        //following is experimental for A* with a cutoff: not executed   
                        //since maxNodes is always -1.
                if (maxNodes > 0 && theOpenNodes.Count > maxNodes)
                {
                    int removed = theOpenNodes.Count - maxNodes;
                    theOpenNodes.RemoveRange(maxNodes, removed);
                }
            }
        }

        public IEnumerable<T> beam()
        {
            reset();
            if (sorter == null)
                throw new GraphException("comparator not supplied for Beam");
            if (maxNodes <= 0)
                throw new GraphException("maxNodes not supplied for Beam");

            nextGeneration = new List<T>(50);
            placeRoot(nextGeneration);
            yield return root;

            while (true)
            {
                T aNode = nextNode(ref theOpenNodes, ref nextGeneration);
                if (aNode == null)
                    break;
                yield return aNode;

                if (nextGeneration.Count > maxNodes)
                {
                    int removed = nextGeneration.Count - maxNodes;
                    nextGeneration.RemoveRange(maxNodes, removed);
                }
            }
        }

        public IEnumerable<T> bestFirst()
        {
            reset();
            if (sorter == null)
                throw new GraphException("comparator not supplied for bestFirst");
                
                    //like beam, except we keep all nodes (as in breadthFirst)
            nextGeneration = new List<T>(15);
            placeRoot(nextGeneration);
            yield return root;

            while (true)
            {
                T aNode = nextNode(ref theOpenNodes, ref nextGeneration);
                if (aNode == null)
                    break;
                yield return aNode;
            }
        }

        public IEnumerable<T> breadthFirst()
        {
            /*
            follow the sibling chain of a node before visiting any of its
            children
            */
            reset();
            if (sorter != null)  //since all nodes will be generated, no reason
                                //to impose sort: just wastes time.
                throw new GraphException("BFS, but sorter was supplied");

            placeRoot(theOpenNodes);
            yield return root;

            while (true)
            {
                T aNode = nextNode(ref theOpenNodes, ref theOpenNodes);
                if (aNode == null)
                    break;
                yield return aNode;
            }
           
        }

        public IEnumerable<T> depthFirst()
        {
            /*
            Follow the firstChild chain before visiting any of its siblings.
            When the chain ends, backtrack to sibling of parent of last node
            visited.
            */

            reset();
            if (endOfGraph)
                    throw new GraphException(
                        "called depthFirst at end of graph");

            lastNode = root;
            yield return root;

            T nextNode;

            while (true)
            {
                nextNode = lastNode.firstChild();
                if (nextNode == null)
                {
                    //out of children
                    nextNode = lastNode;
                    while (true)  //backtracking loop
                    {
                        T sib = nextNode.nextSibling();
                        if (sib != null)
                        {
                            //will get sib, and then kids of sib
                            nextNode = sib;
                            break;
                        }
                        nextNode = nextNode.parent;  //try for sib of parent
                        if (nextNode == null)
                            break;  //all done
                    }
                }
            
                lastNode = nextNode;

                if (lastNode == null)
                {
                    endOfGraph = true;
                    break;
                }

                yield return lastNode;
            }
        }

        public IEnumerable<T> greedy()
        {
            reset();
            if (sorter == null)
                throw new GraphException("comparator not supplied for greedy");
            maxNodes = 1; //like beam, except cutoff is 1 node

            nextGeneration = new List<T>(15);
            placeRoot(nextGeneration);
            yield return root;

            while (true)
            {
                T aNode = nextNode(ref theOpenNodes, ref nextGeneration);
                if (aNode == null)
                    break;
                yield return aNode;

                if (nextGeneration.Count > maxNodes)
                {
                    int removed = nextGeneration.Count - maxNodes;
                    nextGeneration.RemoveRange(maxNodes, removed);
                }
            }
        }

        T nextNode(ref List<T> open, ref List<T> nextGen)
        {
            //this method is used in variants of BFS
            //follow sibling chain

            lastNode = lastNode.nextSibling();

            while (lastNode == null)  
            {
                if (open.Count == 0)
                {
                    if (nextGen != open)
                    {
                        open = nextGen;
                        nextGen = new List<T>(50);
                    }
                }
                if (open.Count == 0)
                {
                    endOfGraph = true;
                    //all done with search
                    break;
                }

                lastNode = open[0].firstChild();
                if (rmvParents)
                {
                    //parent of this processed open node no longer needed.
                    //open[0] itself (parent of current sibling chain) is needed
                    //by application.
                    //woe to the application that trys to chase
                    //the parent chain beyond the immediate parent, in method
                    //nextSibling or in  method firstChild.
                    open[0].parent = null;
                }
                open.RemoveAt(0);
            }

            if (!endOfGraph)
            {
                if (sorter == null || nextGen.Count == 0)
                    nextGen.Add(lastNode);
                else
                {
                    if (maxNodes == 1)  //Greedy:keep only the best one (sorts first)
                    {
                        if (this.Compare(lastNode, nextGen[0]) < 0)
                            nextGen[0] = lastNode;
                    }
                    else
                    {
                        //find the place to insert
                        int hit = nextGen.BinarySearch(lastNode, this);
                        if (hit < 0)
                            hit = ~hit;
                        nextGen.Insert(hit, lastNode);
                    }
                }

                return lastNode;
            }

            return null;
        }

        void placeRoot(List<T> open)
        {
            if (endOfGraph)
                throw new ApplicationException
                    ("called Graph at end of graph");

            lastNode = root;
            open.Add(root);
        }

        public bool quit(T solutionNode)
        {
            /*
            return true if we are assured that aNode is as good as
            the best solution possible.  The caller must assure that
            solutionNode is a solution node.
            */

            if (!isAstar)
                return false;   //quit should not be called unless aStar search

            if (theOpenNodes.Count == 0) //last node in search
                return true;

            if (solutionNode == null)   //courtesy so caller need not test
                return false;
            /*
            We might be in the midst of processing a sibling chain.
            Until we are done with that chain, we might yet find a
            better solution on the sibling chain, even if the current
            best solution is better than the best node in the theOpenNodes.

            The most promising node (which has already been returned, 
            but whose children are next to be examined, after the 
            current sibing chain), is found in theOpenNodes[0].  

            Once our best solution so far discovered
            (passed by user as solutionNode) is better than the parent
            of the theOpenNodes[0], we know it is also better than all
            of the children of theOpenNodes[0].parent, and therefore
            better than all the nodes on the current sibling chain we
            are returning.
            */
            T parentBest = theOpenNodes[0].parent;
            if (parentBest == null)
                return false;

            if (sorter(solutionNode, parentBest) <= 0)
                return true;
            return false;
        }

        void reset()
        {
            lastNode = default(T);
            endOfGraph = false;
            theOpenNodes = new List<T>(10);  
            nextGeneration = null;
            if (root == null)
                endOfGraph = true;
        }

        #region IComparer<T> Members

        public int Compare(T x, T y)
        {
            return sorter(x, y);
        }

        public bool Equals(T x, T y)
        {
            if (x == y)
                return true;
            return sorter(x,y) == 0;
        }

        public int GetHashCode(T obj)
        {
            throw new NotImplementedException();
        }

        #endregion
    }
}
